package com.dyz.leetcode._11_comprehensiveApplication;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
设计并实现一个 TwoSum 的类，使该类需要支持 add 和 find 的操作。

add 操作 - 对内部数据结构增加一个数。
find 操作 - 寻找内部数据结构中是否存在一对整数，使得两数之和与给定的数相等。
示例 1:

add(1); add(3); add(5);
find(4) -> true
find(7) -> false
示例 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false
 */
public class _170_twoSum {
    private List<Integer> nums;

    public _170_twoSum(){
        nums = new ArrayList<>();
    }
    public void add(int value){
        nums.add(value);
    }
    public boolean find(int value) {
        Collections.sort(nums);
        int left= 0;
        int right = nums.size()-1;
        while (left<=right){
            int mid = left+(right-left)/2;
            if(nums.get(mid)==value){
                return true;
            }else if(nums.get(mid)>value){
                right = mid -1;
            }else {
                left = left+1;
            }
        }
        return false;
    }

}
